package mashibing.a_xsb;

import java.util.Arrays;

/**
 * 局部最小值
 *
 * @author yujiafan
 * @version 1.0.0
 * @create 2022-12-22
 */
public class NewClassDay3_02 {

    // 相邻互不相等数组
    public static int[] getArrayNotEqual(int maxLen, int maxValue) {
        int len = (int) (Math.random() * maxLen) + 1;
        int[] arr = new int[len];
        arr[0] = (int) (Math.random() * maxValue);
        for (int i = 1; i < len; i++) {
            do {
                arr[i] = (int) (Math.random() * maxValue);
            } while (arr[i] == arr[i - 1]);
        }
        return arr;
    }

    // 获取局部最小值
    public static int getLocalMinIndex(int[] arr) {
        if (arr == null || arr.length == 0) {
            return -1;
        }
        int len = arr.length;
        if (len == 1) {
            return 0;
        }
        if (len == 2) {
            return arr[0] < arr[1] ? 0 : 1;
        }
//        int index = -1;
        int L = 0;
        int R = len - 1;
        while (L < R - 1) {
            int mid = (L + R) / 2;
            if (arr[mid] < arr[mid - 1] && arr[mid] < arr[mid + 1]) {
                return mid;
            } else {
                if (arr[mid] > arr[mid - 1]) {
                    R = mid - 1;
                } else {
                    L = mid + 1;
                }
            }
        }
        return arr[L] < arr[R] ? L : R;
    }

    // 校验是否为局部最小值
    public static boolean checkLocalMinValue(int[] arr, int index) {
        if (arr == null || arr.length < 2) {
            return true;
        }
        int len = arr.length;
        int L = index - 1;
        int R = index + 1;
        boolean leftIndex = L >= 0 ? arr[L] > arr[index] : arr[0] < arr[1];
        boolean rightIndex = R < len ? arr[R] > arr[index] : arr[len - 2] > arr[len - 1];
        return leftIndex && rightIndex;
    }

    public static void main(String[] args) {
        int testCount = 100000;
        System.out.println("=======================");
        for (int i = 0; i < testCount; i++) {
            int[] arr = getArrayNotEqual(20, 100);
            int index = getLocalMinIndex(arr);
            boolean flag = checkLocalMinValue(arr, index);
            if (!flag) {
                System.out.println("检查错误");
                System.out.println(Arrays.toString(arr));
                System.out.println(index);
                break;
            }
        }
    }
}
